class Node{
  constructor(key, h = 0, left = null, right = null){
    this.key = key
    this.left = left
    this.right = right
    this.h = h
  }
}
function getNewNode(key) {
  return new Node(key, 1);
}
function update_height(root){
  root.h = Math.max(root.left.h, root.right.h) + 1;
}

function predesccessor(root) {
  let temp = root.left;
  while(temp.right) temp = temp.right;
  return temp;
}

function left_rotate(root) {
  let newRoot = root.right;
  root.right = newRoot.left;
  newRoot.left = root;
  update_height(root);
  update_height(newRoot);
  return newRoot;
}
function right_rotate() {
  let newRoot = root.left;
  root.left = newRoot.right;
  newRoot.right = root;
  update_height(root);
  update_height(newRoot);
  return newRoot;
}

Node.prototype.insert = function(root, key) {
  if(!root) return getNewNode(key);
  if(root.key === key) return root;
  if(key < root.key) {
    root.left = this.insert(root.left, key);
  } else {
    root.right = this.insert(root.right, key);
  }
  
  update_height(root);
  return maintain(root);
}

Node.prototype.erase = function(root, key) {
  if(!root) return root;
  if(key < root.key) {
    root.left = this.erase(root.left, key);
  } else if(key > root.key){
    root.right = this.erase(root.right, key);
  } else {
    if(!root.left && !root.right) {
      delete root;
      return null;
    } else if(!root.left || !root.right){
      let temp = root.left ? root.left : root.right;
      delete root;
      return temp;
    } else {
      let temp = predesccessor(root);
      root.key = temp.key;
      root.left = this.erase(root.left, temp.key);
    }
  }

  update_height(root);
  return maintain(root);
}

// root: 最小的失衡节点
// LL LR RR RL
Node.prototype.maintain = function(root) {
  if(Math.abs(root.left.h - root.right.h) < 2) return root;
  if(root.left.h > root.right.h){ // LL / LR
    if(root.left.right.h > root.left.left.h) { // LR
      root.left = left_rotate(root.left);
    }
    root = right_rotate(root);
  } else { // RR / RL
    if(root.right.left.h > root.right.right.h) { // RL
      root.right = right_rotate(root.right);
    }
    root = left_rotate(root);
  }
  return root;
}